package leetcode.code0743;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int networkDelayTime(int[][] times, int n, int k) {
		// hash时间
		int[][] ws = new int[101][101];
		// 构建邻接边
		Map<Integer, List<Integer>> edges = new HashMap<>();
		for (int i = 1; i <= n; i++) {
			edges.put(i, new ArrayList<>());
		}
		for (int i = 0; i < times.length; i++) {
			int[] time = times[i];
			int u = time[0], v = time[1], w = time[2];
			ws[u][v] = w;
			edges.get(u).add(v);
		}
		// 抵达的最早时间
		int[] arrival = new int[n + 1];
		Arrays.fill(arrival, Integer.MAX_VALUE);
		arrival[k] = 0;
		// queue.add(new int[]{抵达点，抵达时间})
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
		queue.add(new int[] { k, 0 });
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int u = cur[0], w = cur[1];
			// 早就抵达过了，舍弃
			if (w > arrival[u]) {
				continue;
			}
			List<Integer> nexts = edges.get(u);
			for (int next : nexts) {
				int t = w + ws[u][next];
				// 更新最早抵达时间
				if (t < arrival[next]) {
					arrival[next] = t;
					queue.add(new int[] { next, t });
				}
			}
		}
		int ans = 0;
		for (int i = 1; i < arrival.length; i++) {
			int t = arrival[i];
			if (t == Integer.MAX_VALUE) {
				return -1;
			}
			ans = Math.max(ans, t);
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(2, this.networkDelayTime(H.str2array1("[[2,1,1],[2,3,1],[3,4,1]]"), 4, 2));
		H.compare(1, this.networkDelayTime(H.str2array1("[[1,2,1]]"), 2, 1));
		H.compare(-1, this.networkDelayTime(H.str2array1("[[1,2,1]]"), 2, 2));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
